package com.sheng.leetcode.year2023.month02.day04;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2023/02/06
 * <p>
 * 1798. 你能构造出连续值的最大数目<p>
 * <p>
 * 给你一个长度为 n 的整数数组 coins ，它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。<p>
 * 如果你从这些硬币中选出一部分硬币，它们的和为 x ，那么称，你可以 构造 出 x 。<p>
 * 请返回从 0 开始（包括 0 ），你最多能 构造 出多少个连续整数。<p>
 * 你可能有多个相同值的硬币。<p>
 * <p>
 * 示例 1：<p>
 * 输入：coins = [1,3]<p>
 * 输出：2<p>
 * 解释：你可以得到以下这些值：<p>
 * - 0：什么都不取 []<p>
 * - 1：取 [1]<p>
 * 从 0 开始，你可以构造出 2 个连续整数。<p>
 * <p>
 * 示例 2：<p>
 * 输入：coins = [1,1,1,4]<p>
 * 输出：8<p>
 * 解释：你可以得到以下这些值：<p>
 * - 0：什么都不取 []<p>
 * - 1：取 [1]<p>
 * - 2：取 [1,1]<p>
 * - 3：取 [1,1,1]<p>
 * - 4：取 [4]<p>
 * - 5：取 [4,1]<p>
 * - 6：取 [4,1,1]<p>
 * - 7：取 [4,1,1,1]<p>
 * 从 0 开始，你可以构造出 8 个连续整数。<p>
 * <p>
 * 示例 3：<p>
 * 输入：nums = [1,4,10,3,1]<p>
 * 输出：20<p>
 * <p>
 * 提示：<p>
 * coins.length == n<p>
 * 1 <= n <= 4 * 10^4<p>
 * 1 <= coins[i] <= 4 * 10^4<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/maximum-number-of-consecutive-values-you-can-make">1798. 你能构造出连续值的最大数目</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1798 {

    @Test
    public void test01() {
//        int[] coins = {1, 3};
//        int[] coins = {1, 1, 1, 4};
        int[] coins = {1, 4, 10, 3, 1};
        System.out.println(new Solution().getMaximumConsecutive(coins));
    }
}

class Solution {
    public int getMaximumConsecutive(int[] coins) {
        int res = 1;
        Arrays.sort(coins);
        for (int i : coins) {
            if (i > res) {
                break;
            }
            res += i;
        }
        return res;
    }
}

// 超时
/*
class Solution {
    public int getMaximumConsecutive(int[] coins) {
        int n = coins.length;
        // 从数组 coins 中取出一部分元素，它们的和为 x，则代表可以构造出 x，求出从 0 开始能构造出的最大连续整数
        // 数组 coins 的元素一定是正整数
        Arrays.sort(coins);
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            int sum = 0;
            int left = 0;
            int right = 0;
            while (sum != i) {
                while (sum < i && right < n) {
                    sum += coins[right++];
                }
                left = right - 1;
                while (sum > i && left >= 0) {
                    if (sum - coins[left] >= i) {
                        sum -= coins[left--];
                    } else {
                        left--;
                    }
                }
                if (sum != i) {
                    return i;
                }
            }
        }
        return 0;
    }
}
*/
